package basic.study.wantOffer.chapter2;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;

/**
 * @author Kevin
 * @date 2020/4/27 12:08
 * 一个长度为n的数组里所有数字都在0~n-1范围内，找出数组中重复的数字
 */
public class Problem3 {
    //方法1：先对数组排序
    public boolean solution1(int[] arr) {
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            if (i+1 < arr.length && arr[i] == arr[i+1]) {
                return true;
            }
        }
        return false;
    }
    //方法2：哈希表
    public boolean solution2(int[] arr) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (!set.contains(arr[i])) {
                set.add(arr[i]);
            } else {
                return true;
            }
        }
        return false;
    }

    //方法3：下标映射
    public boolean solution3(int[] arr) {
        if (arr == null || arr.length <= 0) {
            return false;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0 || arr[i] > arr.length -1) {
                return false;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            while (arr[i] != i) {
                if (arr[i] == arr[arr[i]]) {
                    return true;
                } else {
                    //swap arr[i] and arr[arr[i]]
                    int temp = arr[i];
                    arr[i] = arr[arr[i]];
                    arr[arr[i]] = temp;
                }
            }
        }
        return false;
    }

    /**
     * 题目二：不修改数组找出重复的数字
     * 长度为n+1的数组里的所有数字都在1~n+1的范围内
     */
    //方法1：使用辅助数组
    //空间复杂度O(n)，时间复杂度O(n)
    public boolean solution4(int[] arr) {
        if (arr == null || arr.length <= 0) {
            return false;
        }
        int n = arr.length -1;
        int[] check = new int[n+1];
        Arrays.fill(check, 0);
        for (int val: arr) {
            if (check[val] != 0) {
                return true;
            } else {
                check[val] += 1;
            }
        }
        return false;
    }

    //方法2：二分查找法(以时间换空间)
    //1~n的数子从中间数字n分开为两部分，每部分若数目超过m则一定包含重复数字
    //空间复杂度O(1)，时间复杂度O(nlogn)
    public int solution5(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int start = 0;
        int end = arr.length -1;
        while (start <= end) {
            int middle = start + (end - start)>>1;
            int count = countRange(arr, start, middle);
            if (start == end) {
                if (count > 1) {
                    return start;
                } else {
                    break;
                }
            }
            if (count > (middle - start + 1)) {
                end = middle;
            } else {
                start = middle + 1;
            }
        }

        return -1;
    }

    public int countRange(int[] arr, int start, int end) {
        if (arr == null) return 0;

        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= start && arr[i] <= end) {
                count++;
            }
        }
        return count;
    }
}
